package com.zjsru.oneday202208;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: likew
 * @Date: 2022/8/12
 * 用户分组
 *
 * 输入：groupSizes = [3,3,3,3,3,1,3]
 * 输出：[[5],[0,1,2],[3,4,6]]
 * 解释：
 * 第一组是 [5]，大小为 1，groupSizes[5] = 1。
 * 第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
 * 第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。
 * 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
 *
 * 输入：groupSizes = [2,1,3,3,3,2]
 * 输出：[[1],[0,5],[2,3,4]]
 */
public class GroupThePeople {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer,List<Integer>> map = new HashMap<>();
        for (int i = 0; i < groupSizes.length; i++) {
            List<Integer> list = map.getOrDefault(groupSizes[i],new ArrayList<>());
            list.add(i);
            map.put(groupSizes[i],list);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int num:map.keySet()) {
            List<Integer> list = map.get(num), cur = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                cur.add(list.get(i));
                if(cur.size() == num){
                    ans.add(cur);
                    cur = new ArrayList<>();
                }
            }
            
        }
        return ans;
    }
    
    public static void main(String[] args) {
        GroupThePeople groupThePeople = new GroupThePeople();
        int[] groupSizes = new int[]{2,1,3,3,3,2};
        System.out.println(groupThePeople.groupThePeople(groupSizes));
    }
}
